#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 410;
int f[N][N], g[N][N];
int n, m;
int floyd(int d[][N])
{
	if (d[1][n] == 1)return 1;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	return d[1][n];
}	
int main()
{
	cin >> n >> m;
	memset(f, 0x3f, sizeof(f));
	memset(g, 0x3f, sizeof(g));
	while (m--) {
		int a, b;
		cin >> a >> b;
		f[a][b] = f[b][a] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && f[i][j] != 1) {
				g[i][j] = g[j][i] = 1;
			}
		}
	}
	//cout<<g[1][4]<<endl;
	int ans1 = floyd(f);
	//cout<<"ans1  "<<ans1<<endl;
	int ans2 = floyd(g);
	//cout<<"ans2  "<<ans2<<endl;
	int ma = max(ans1, ans2);
	if (ma == 0x3f3f3f3f)ma = -1;
	cout << ma << endl;
	return 0;
}